/**
 * 判断二叉树是否为完全二叉树
 * 这里使用的层序遍历的方法
 */

#include"BiTree.h"
#include<queue>
using namespace std;
bool isComplete(BiTree*root){
    queue<BiTree*> q;
    BiTree* p;
    if(!root){
        return true;//空树为满二叉树
    }
    q.push(root);
    while (!q.empty())//如果队列不为空，就弹出一个元素
    {
        p=q.front();
        q.pop();
        if(p){//如果这个元素存在，就应该将他的左右节点插入队列
            q.push(p->left);//有可能将null放入队列，下一轮循环会判断
            q.push(p->right);
        }else{//如果这个元素是空
            while (!q.empty())//将队列的元素一直弹出
            {
                p=q.front();
                q.pop();
                if(p){//节点非空，则为非完全二叉树
                    return false;
                }
            }
            
        }
    }
    return true;
    
}